1. Technical Field of the Invention
The present invention relates to a three-dimensional shape data position matching method and device for measuring a non-moving three-dimensional shape from a plurality of measuring positions, and for combining and position matching the distance data thereof.
2. Description of the Related Art
In the present invention, the estimation of geometric positional relationships of a plurality of range images that are obtained by measuring a non-moving three-dimensional shape from multiple observation points is termed “position matching.”
Three-dimensional shape measuring technologies are becoming more prevalent, and three-dimensional shape data is used in a variety of application fields, such as measuring shapes inmachine components/workpieces, self-position identification in mobile robots, and topographical and structural measurements, and the like.
When measuring the three-dimensional shape of an object and restoring that three-dimensional shape, it is possible to acquire surface data of the surface facing the observation point (measurement position) when measuring from a single observation point, but not possible to measure the back surface of the object. Because of this, reproducing a three-dimensional shape requires measurement from a plurality of observation points, and requires precise position matching of the measurement results.
Position matching of data acquired from a plurality of observation points requires explicit definition of the positional relationship between the observation point and the measured object. Methods for obtaining the positional relationships between the observation point and the object to be measured include methods wherein the object is placed on a stage and rotated, and methods wherein the observation point is held on an arm, or the like, that has a mechanical linkage, but in both cases the precision of the positional relationships is limited. Additionally, even assuming precision were adequate, there is still a limit to the size of the object to be measured.
Given this, as means wherein the positional relationship is not affected and wherein there is also no limit to the size of the object to be measured, various means have been proposed wherein measured data obtained earlier and measured data obtained later are compared and matched.
Of these, when a corresponding point is already known, this can be solved easily as a problem of minimizing the square error through rotation and translation. However, typically corresponding points are not known in advance.
Matching using invariant features, the direct method, and ICP algorithms have been proposed (in, for example, non-patent documents 1 and 2) as means for position matching when corresponding points are not known in advance.
In “matching using invariant features,” matching of two data are performed using local invariant feature points in the shape (such as derivative features).
In the “direct method,” an optical flow in a two-dimensional image is calculated for a three-dimensional image.
In the “ICP (Iterative Closest Points) Algorithm,” the closest points in data measured later relative to data that has been measured earlier are calculated, and rotations and translations are performed to find a solution wherein the state having the minimum summation of distances is set as the matching state.
Additionally, non-patent document 3 is disclosed as a technology relating to the present invention.
(Non-Patent Document 1)
Takeshi Masuda, et al, “Shape Model Generation from Multiple Range Images”
(Non-Patent Document 2)
Paul J. Besl, “A Method for Registration of 3-D Shapes,” IEEE Transactions of Pattern Analysis and Mechanical Intelligence, Vol. 14, No. 2, February 1992
(Non-patent Document 3)
Sekimoto Kiyohide, et al., “Development of a Three-Dimensional Laser Radar,” Ishikawaj ima-Harima Engineering Review, vol. 43, No. 4 (2003-7)
When range sensors are used, such as the three-dimensional laser radar, the measurement points on the three-dimensional object being measured form a set of points that are dispersed in the horizontal direction and in the vertical direction. When it comes to the spacing of this point set, if the distance from the measurement point is, for example, 50 m, then the spacing of the points to be measured will reach, for example, about 315 mm in the horizontal direction and about 525 mm in the vertical direction.
Furthermore, when measuring a non-moving three-dimensional shape from a plurality of measurement points, then normally the positions of the points to be measured are different for each measurement point with a range sensor such as a three-dimensional laser radar.
Moreover, with this type of range sensor, typically there is error of about ±20 cm in the measured distances.
Consequently, there are the following constraint conditions A through C when a range sensor such as a three-dimensional laser radar is used.
Condition A: The number of points in the measured data be low (for example, 166×50 points in one frame).
Condition B: There is error in the measured data (for example, about ±20 cm in the measured distances).
Condition C: The measured data is not limited to measuring the same measurement point.
That is, the range data that is obtained is a set of points that are dispersed in the horizontal direction and the vertical direction. Since the measured position is different for each measurement, there are not corresponding points, and measured distance includes a relatively large error.
When this type of range data is processed in the “matching using invariant features” or “direct method,” the point set is dispersed, the number of measurement points is low, there are no corresponding points, and there is a large amount of measurement error, so that it is essentially impossible to perform position matching accurately.
Additionally, although in theory it is possible to perform point set position matching using the ICP algorithm, there are the following problems:
(1) Cumulative Error
The ICP algorithm is the means for superimposing two distance data, and even though the earlier data and the later data are compared repetitively and the differences are integrated, there are essentially no corresponding points, so the error is cumulative.
(2) High Calculation Amount
The ICP algorithm is an iterative calculation, so that the calculation amount is large. That is, the ICP algorithm requires searching for model data corresponding to each of the data points in the measured data, so the calculation amount increases as the numbers of model data points and measured data points increase. Specifically, if the number of model data points is M and the number of measured data points is N, then the calculation order for the total search time is O (M×N).
(3) Not Suitable if there are Few Measurement Points
The ICP algorithm is used for dense range data, so when the point set is dispersed and spatially sparse, the algorithm will converge to incorrect results.